import java.util.Arrays;

public class Sort {
    public static void BubbleSort(int[] array){
        int lastIndex = array.length-1;
        int swapIndex = 0;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int i = 0;i<lastIndex;i++){
                if(array[i]>array[i+1]){
                    swap(array,i,i+1);
                    flag = true;
                    swapIndex = i;
                }
            }
            lastIndex = swapIndex;
        }
    }
    public static void selectionSort(int[] array){
        int minIndex = 0;
        boolean flag = false;
        for(int i = 0;i<array.length;i++){
            minIndex = i;
            flag = false;
            for(int j = i+1;j< array.length;j++){
                if(array[minIndex]>array[j]){
                    minIndex = j;
                    flag = true;
                }
            }
            if(flag){
                swap(array,minIndex,i);
            }
        }
    }
    public static void selectionSort2(int[] arr){
            int minIndex, maxIndex;
            // i 只需要遍历一半
            for (int i = 0; i < arr.length / 2; i++) {
                minIndex = i;
                maxIndex = i;
                for (int j = i + 1; j < arr.length - i; j++) {
                    if (arr[minIndex] > arr[j]) {
                        // 记录最小值的下标
                        minIndex = j;
                    }
                    if (arr[maxIndex] < arr[j]) {
                        // 记录最大值的下标
                        maxIndex = j;
                    }
                }
                // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
                if (minIndex == maxIndex) break;
                // 将最小元素交换至首位
                swap(arr,minIndex,i);
                // 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
                if (maxIndex == i) maxIndex = minIndex;
                // 将最大元素交换至末尾
                int lastIndex = arr.length - 1 - i;
                swap(arr,lastIndex,maxIndex);
            }
        }
    private static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
    public static void insertSort(int[] array){
        for(int i = 1;i<array.length;i++){
            int j =i;
            while(j>=1&&array[j-1]>array[j]){
                swap(array,j-1,j);
                j--;
            }
        }
    }
    public static void insertSort2(int[] array){
        for(int i = 1;i<array.length;i++){
            int cur = array[i];
            int j = i-1;
            while(j>=0&&array[j]>cur){
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = cur;
        }
    }
    public static void shellSort(int[] arr) {
        // 间隔序列，在希尔排序中我们称之为增量序列
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 分组
            for (int groupStartIndex = 0; groupStartIndex < gap; groupStartIndex++) {
                // 插入排序
                for (int currentIndex = groupStartIndex + gap; currentIndex < arr.length; currentIndex += gap) {
                    // currentNumber 站起来，开始找位置
                    int currentNumber = arr[currentIndex];
                    int preIndex = currentIndex - gap;
                    while (preIndex >= groupStartIndex && currentNumber < arr[preIndex]) {
                        // 向后挪位置
                        arr[preIndex + gap] = arr[preIndex];
                        preIndex -= gap;
                    }
                    // currentNumber 找到了自己的位置，坐下
                    arr[preIndex + gap] = currentNumber;
                }
            }
        }
    }
    public static void shell(int[] array){
        for(int gap = array.length/2 ; gap > 0 ; gap /= 2){//这一行仅仅是分组
            for(int groupStartIndex = 0; groupStartIndex < gap;groupStartIndex++){//前部分，每一个都是一个组的开始，所以每一组结束到下一组的开始就是++
                //；前面总共分了gap个组，所以前gap个元素就是组头
                for(int currentIndex = groupStartIndex + gap;currentIndex<array.length;currentIndex+=gap){
                    int currentNumber = array[currentIndex];
                    int preIndex = currentIndex - gap;//一组中，前面的元素
                    while(preIndex>=groupStartIndex&&currentNumber<array[preIndex]){
                        array[preIndex+gap] = array[preIndex];
                        preIndex-=gap;
                    }
                    array[preIndex+gap] = currentNumber;

                }
            }

        }
    }
    public static int partition(int[] array,int low ,int high){
        int i = low;
        int key = array[low];
        while(low<high){
            while(low<high&&array[high]<=key){
                high--;
            }

            while(low<high&&array[low]>=key){
                low++;
            }

           swap(array,low,high);
        }
        swap(array,low,i);
        return low;
    }
    public static int partition1(int[] array,int low ,int high){
        int i = low;
        int key = array[low];
        while(low<high){
            while(low<high&&array[high]>=key){
                high--;
            }
            array[low] = array[high];
            while(low<high&&array[low]<=key){
                low++;
            }

            array[high] = array[low];
        }
        array[low] = key;
        return low;
    }
    public static void patition(int[] array,int low,int right){

    }
    public static void quick(int[] array,int left,int right){
        if(left>=right){
            return ;
        }
        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);

    }
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }




    public static void main(String[] args) {
        int[] array = new int[]{1,4,5,2,7,3,94,75,89,11,10,38,29,91,44,45};
        System.out.println(Arrays.toString(array));
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
